/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/**
 * @ClassName   : Leetcode538 
 * @author      : ganwei 
 * @date        : 2020年5月3日
 * @Description : Leetcode538 把二叉搜索树转换为累加树
 */
public class Leetcode0538 {
	private int sum = 0;
	/**
	 * -解题思路
	 * -1.递归思路，先计算又子树，更新和，然后计算左子树
	 */
    public TreeNode convertBST(TreeNode root) {
    	
    	if(root != null) { 	
    		convertBST(root.right);
    		sum += root.val;
    		root.val = sum;
    		convertBST(root.left);
    	}
    	return root;
    }
    

    
    public static void main(String[] args) {
    	TreeNode t1 = new TreeNode(5);
    	TreeNode t2 = new TreeNode(3);
    	TreeNode t3 = new TreeNode(7);
    	TreeNode t4 = new TreeNode(2);
    	TreeNode t5 = new TreeNode(6);
    	t1.left = t2;
    	t1.right = t3;
    	t2.left = t4;
    	t3.left = t5;
    	Leetcode0538 l538 = new Leetcode0538();
    	l538.convertBST(t1);
    	System.out.println(t1.val);
    	System.out.println(t2.val);
    	System.out.println(t3.val);
    	System.out.println(t4.val);
    	System.out.println(t5.val);
    	int i = 1;
    	System.out.println(i+=1);
    }
}
